/*
  ! 前途似海，来日方长。
  ! Created: 2024/12/26 08:27:17
*/
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
// #define int long long
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for (int i = (x); i <= (y); i++)
#define pre(i, x, y) for (int i = (x); i >= (y); i--)
inline void JYFILE19();

using i64 = long long;
using pii = pair<int, int>;

bool ST;
const int N = 2e6 + 10;
const int mod = 998244353;

int n, k, q, m, a[N], id[N];
i64 all, num[N], sum[N];

struct Mat {
  i64 a[7][7]{};
  inline Mat operator*(const Mat& tmp) const {
    Mat c;
    fro(i, 0, 6) fro(k, 0, 6) fro(j, 0, 6) c.a[i][j] += a[i][k] * tmp.a[k][j];
    fro(i, 0, 6) fro(j, 0, 6) c.a[i][j] %= mod;
    return c;
  }
  inline void mul(const Mat& tmp) {
    Mat c;
    fro(k, 0, 6) fro(j, 0, 6) c.a[0][j] += a[0][k] * tmp.a[k][j];
    fro(i, 0, 6) fro(j, 0, 6) a[i][j] = c.a[i][j] % mod;
  }
  inline void init() { fro(i, 0, 6) a[i][i] = 1; }
} pw[30];
struct Que {
  int x, y, id, op;
  inline bool operator<(const Que& tmp) const { return x < tmp.x; }
} d[N];
struct Tree {
  i64 t[N];
  inline int lb(int x) { return x & (-x); }
  inline void upd1(int x, int k) { while (x <= n) t[x] += k, x += lb(x); }
  inline auto ask1(int x) { i64 r = 0; while (x) r += t[x], x -= lb(x); return r; }
  inline void upd2(int x, int k) { while (x) t[x] += k, x -= lb(x); }
  inline auto ask2(int x) { i64 r = 0; while (x <= n) r += t[x], x += lb(x); return r; }
} t1, t2;

inline i64 power(i64 x, i64 y) {
  i64 res = 1;
  while (y) {
    if (y & 1) res = res * x % mod;
    x = x * x % mod, y /= 2;
  }
  return res;
}
inline Mat power(Mat x, i64 y) {
  Mat res;
  res.init();
  while (y) {
    if (y & 1) res = res * x;
    x = x * x, y /= 2;
  }
  return res;
}
inline i64 C2(i64 x) { return x * (x - 1) / 2 % mod; }
inline void init() {
  fro(i, 2, n)(all += 1ll * (i + 2) * (i - 1) / 2 % mod) %= mod;
  // AB BA AO BO OA OB OO
  pw[0] = {{{C2(n - 2), 1, n - 2, 0, 0, n - 2, 0},
            {1, C2(n - 2), 0, n - 2, n - 2, 0, 0},
            {1, 0, C2(n - 2) + n - 3, 1, 1, 0, n - 3},
            {0, 1, 1, C2(n - 2) + n - 3, 0, 1, n - 3},
            {0, 1, 1, 0, C2(n - 2) + n - 3, 1, n - 3},
            {1, 0, 0, 1, 1, C2(n - 2) + n - 3, n - 3},
            {0, 0, 1, 1, 1, 1, C2(n - 2) + 2 * n - 7}}};
  fro(i, 1, 29) pw[i] = pw[i - 1] * pw[i - 1];
}
inline void sol(int p) {
  Mat d;
  d.a[0][0] = 1;
  fro(i, 0, 29) if (((k - p) >> i) & 1) d.mul(pw[i]);
  i64 ans = d.a[0][6] * C2(n) % mod * power(2, mod - 2) % mod;
  (d.a[0][2] *= power(n - 2, mod - 2)) %= mod;
  (d.a[0][3] *= power(n - 2, mod - 2)) %= mod;
  i64 u = num[id[p]], v = sum[id[p]] + num[id[p]];
  u %= mod, v %= mod;
  (ans += (d.a[0][1] + d.a[0][2] * n + d.a[0][3] * (n - 4)) % mod * u) %= mod;
  (ans += (d.a[0][3] - d.a[0][2]) * v) %= mod;
  u = (1ll * n * (n - 1) / 2 - u) % mod, v = (all - v) % mod;
  (ans += (d.a[0][0] + d.a[0][3] * n + d.a[0][2] * (n - 4)) % mod * u) %= mod;
  (ans += (d.a[0][2] - d.a[0][3]) * v) %= mod;
  ans = ans * power(power(C2(n), k - p), mod - 2) % mod;
  cout << (ans % mod + mod) % mod << "\n";
}
inline void cdq(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1, it;
  cdq(l, mid), cdq(mid + 1, r);
  it = l;
  fro(i, mid + 1, r) {
    while (it <= mid && d[it].x < d[i].x)
      t1.upd1(d[it].y, d[it].op), it++;
    num[d[i].id] += t1.ask1(d[i].y - 1) * d[i].op;
  }
  fro(i, l, it - 1) t1.upd1(d[i].y, -d[i].op);
  it = mid;
  pre(i, r, mid + 1) {
    while (it >= l && d[it].x > d[i].x)
      t1.upd2(d[it].y, d[it].op), it--;
    num[d[i].id] += t1.ask2(d[i].y + 1) * d[i].op;
  }
  fro(i, it + 1, mid) t1.upd2(d[i].y, -d[i].op);
  inplace_merge(d + l, d + mid + 1, d + r + 1);
}

signed main() {
  JYFILE19();
  cin >> n >> k >> q;
  fro(i, 1, n) cin >> a[i];
  init();
  fro(i, 1, n) ++m, d[m] = {i, a[i], m, 1};
  fro(i, 1, n) {
    i64 u, v;
    t1.upd1(a[i], 1);
    t2.upd1(a[i], i);
    u = t1.ask1(a[i] - 1);
    v = t2.ask1(a[i] - 1);
    sum[i] = (u * i - v);
  }
  fill(t1.t + 1, t1.t + n + 1, 0);
  fill(t2.t + 1, t2.t + n + 1, 0);
  id[0] = m;
  fro(i, 1, q) {
    int x, y;
    cin >> x >> y;
    if (x > y) swap(x, y);
    ++m, d[m] = {y, a[y], m, -1};
    ++m, d[m] = {x, a[x], m, -1};
    swap(a[x], a[y]);
    ++m, d[m] = {x, a[x], m,  1};
    ++m, d[m] = {y, a[y], m,  1};
    sum[id[i] = m] = 1ll * (y - x) * (a[y] - a[x]);
  }
  cdq(1, m);
  fro(i, 1, m) sum[i] += sum[i - 1];
  fro(i, 1, m) num[i] += num[i - 1];
  fro(i, 0, q) sol(i);
  return 0;
}

bool ED;
inline void JYFILE19() {
  freopen("random.in", "r", stdin);
  freopen("random.out", "w", stdout);
  srand(random_device{}());
  ios::sync_with_stdio(0), cin.tie(0);
  double MIB = fabs((&ED - &ST) / 1048576.), LIM = 512;
  cerr << "MEMORY: " << MIB << endl, assert(MIB <= LIM);
}